package org.zhangyp.n03algorithm.n04Greedy;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Interval {
    int start;
    int end;

    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {
        return "{" +
                "start=" + start +
                ", end=" + end +
                '}';
    }
}

public class Greedy {
    /**
     * 分发饼干
     * 每个孩子都有一个满足度，每个饼干都有一个大小，只有饼干的大小大于等于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。
     *
     * @param g
     * @param s
     * @return
     */
    public static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int res = 0;
        int si = 0;
        for (int a : g) {
            for (; si < s.length;) {
                int b = s[si];
                if (b >= a) {
                    res++;
                    si++;
                    break;
                } else {
                    si++;
                }
            }
        }
        return res;
    }

    /**
     * 计算让一组区间不重叠所需要移除的区间个数
     *
     * @return
     */
    public static int eraseOverlapIntervals() {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt(); //几个区间
        Interval[] intervals = new Interval[n];
        if (intervals.length == 0) {
            return 0;
        }
        for (int i = 0; i < n; i++) {
            int a = cin.nextInt();
            int b = cin.nextInt();
            Interval interval = new Interval(a, b);
            intervals[i] = interval;
        }
        //Arrays.sort(intervals, Comparator.comparingInt(o -> o.end));
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.end - o2.end;
            }
        });
        System.out.println(Arrays.toString(intervals));
        int cnt = 1;
        int end = intervals[0].end;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < end) {
                continue;
            }
            end = intervals[i].end;
            cnt++;
        }
        return intervals.length - cnt;
    }

    public static void main(String[] args) {
        /*int result = eraseOverlapIntervals();
        System.out.println(result);*/
        int[] g = {1, 2, 3};
        int[] s = {1, 1};
        System.out.println(findContentChildren(g, s));
    }


}
